#python3 code
'''
email: chenyan@feling.net

二分查找

'''

def binary_search(x,l):
    '''
    return the index of num:x in list:l  
    -1 if not exists
    >>> x = 3
    >>> l = [0,1,2,3,4,5,6,7,8,9]
    >>> binary_search(x,l)
    3
    >>> binary_search(4,l)
    4
    >>> binary_search(0,[0,])
    0
    >>> binary_search(0,[0,1])
    0
    >>> binary_search(0,[-1,0])
    1
    >>> binary_search(0,[-2,-1,0])
    2
    >>> binary_search(2,[0,1])
    -1
    >>> binary_search(1,[0,2])
    -1
    >>> binary_search(1,[3,4])
    -1
    '''
    begin = 0
    end = len(l)
    while begin<end:
        median = (begin+end)//2
        if x==l[median]:
            return median
        if x<l[median]:
            end = median
        else:
            begin = median+1
    return -1

if __name__=='__main__':
    import doctest
    doctest.testmod()

